package LinkedListReverse;

class Node{
	int val;
	Node pre;
	Node nxt;
	public Node(int v){
		val = v;
		pre = null;
		nxt = null;
	}
}

public class Main {
    public static void main(String[] args) {
    	//a链表
    	Node aLeft = new Node(-1);
    	Node aRight = new Node(-1);
    	
    	aLeft.nxt = aRight;
    	aRight.pre = aLeft;
    	for(int i=1;i<=3;i++) {
    		//right端前加节点
    		Node temp = new Node(i);
    		aRight.pre.nxt = temp;
    		temp.pre = aRight.pre;
    		temp.nxt = aRight;
    		aRight.pre = temp;
    	}
    	
    	//b链表
    	Node bLeft = new Node(-1);
    	Node bRight = new Node(-1);
    	bLeft.nxt = bRight;
    	bRight.pre = bLeft;
    	for(int i=5;i<=7;i++) {
    		//right端前加节点
    		Node temp = new Node(i);
    		bRight.pre.nxt = temp;
    		temp.pre = bRight.pre;
    		temp.nxt = bRight;
    		bRight.pre = temp;
    	}
    		
    	//b链表反向连在a链表后面，复杂度O(1)
    	//a最后一个节点的nxt指向b的最后一个节点
    	aRight.pre.nxt = bRight.pre;
    	//b最后一个节点的nxt指向a的最后一个节点
    	bRight.pre.nxt = aRight.pre;
    	//b第一个节点的前驱指向aRight
    	bLeft.nxt.pre = aRight;
    	//aRight的pre指向b的最后一个节点
    	aRight.pre = bLeft.nxt; 
    	//不再引用b链表
    	bLeft.nxt = bRight;
    	bRight.pre = bLeft;
    	
    	//a链表逆向出队
    	while(aRight.pre!=aLeft) {//不为空则继续
    		int k = aRight.pre.val;
    		Node p = aRight.pre;  //p引用最后一个节点
    		if(aRight.pre.pre == aRight) {
    			//最后一个节点是逆序的
        		//因为节点逆序了，aRight的pre指向最后一个节点的nxt指向
    			aRight.pre = aRight.pre.nxt;
    			
    			if(aRight.pre.pre == p) {
    				//最后一个节点的下一个节点还是逆序的
    				aRight.pre.pre = aRight;
    			}else {
    				//最后一个节点的下一个节点是正序的
    				aRight.pre.nxt = aRight;
    			}
        	}else {
        		//最后一个节点是正序的
        		//因为节点正序，aRight的pre指向最后一个节点的pre指向
        		aRight.pre = aRight.pre.pre;
        		
        		if(aRight.pre.pre == p) {
    				//最后一个节点的下一个节点还是逆序的
    				aRight.pre.pre = aRight;
    			}else {
    				//最后一个节点的下一个节点是正序的
    				aRight.pre.nxt = aRight;
    			}
        	}
    		//不再引用p，最后一个节点被删除
    		//输出最后一个节点的值
    		System.out.println(k);
    	}
    	
    	System.out.print("done!");
    }
}